package leetcode;

public class _0042 {
    /**
     * 接雨水
     */
    class Solution {
        public int trap(int[] height) {
            int n = height.length;
            int[] pre = new int[n];
            int[] suf = new int[n];
            int ans =0;
            pre[0] = height[0];
            for(int i=1;i<n;i++){
                pre[i] = Math.max(height[i],pre[i-1]);
            }
            suf[n-1]= height[n-1];
            for(int i=n-2;i>=0;i--){
                suf[i] = Math.max(height[i],suf[i+1]);
            }
            for(int i=0;i<n;i++){
                ans+=(int)Math.min(pre[i],suf[i])-height[i];
            }
            return ans;
        }
    }

    /**
     * 双指针
     */
    class Solution2 {
        public int trap(int[] height) {
            int n = height.length;
            int ans=0;
            int pre=0;
            int suf=0;
            int left = 0;
            int right = n-1;
            while(left<right){
                pre = Math.max(pre,height[left]);
                suf = Math.max(suf,height[right]);
                if(pre<suf){
                    ans+=pre-height[left];
                    left++;
                }else{
                    ans+=suf-height[right];
                    right--;
                }
            }
            return ans;
        }
    }
}
